package Leetcode.数组字符串;

import java.util.Arrays;

/**
 * @ClassName 任意子数组和的绝对值的最大值
 * @since: 2023/8/8 21:06
 * @auth: kirito
 * @description:
 * 给你一个整数数组 nums 。一个子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的 和的绝对值 为 abs(numsl + numsl+1 + ... + numsr-1 + numsr) 。
 *
 * 请你找出 nums 中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值 。
 *
 * abs(x) 定义如下：
 *
 * 如果 x 是负整数，那么 abs(x) = -x 。
 * 如果 x 是非负整数，那么 abs(x) = x 。
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,-3,2,3,-4]
 * 输出：5
 * 解释：子数组 [2,3] 和的绝对值最大，为 abs(2+3) = abs(5) = 5 。
 *
 * 一个变量绝对值的最大值，可能是这个变量的最大值的绝对值，
 * 也可能是这个变量的最小值的绝对值。题目要求任意子数组和的绝对值的最大值，
 * 可以分别求出子数组和的最大值
 *
 * 思路参考最大子数组和
 **/
//动态规划
public class 任意子数组和的绝对值的最大值 {
    public static int maxAbsoluteSum(int[] nums) {
        int positiveMax = 0, negativeMin = 0;
        int positiveSum = 0, negativeSum = 0;
        for (int num : nums) {
            positiveMax = Math.max(num, positiveMax+num);
            positiveSum = Math.max(positiveSum, positiveMax);

            negativeMin = Math.min(num, negativeMin + num);
            negativeSum = Math.max(negativeSum, negativeMin);
        }
        return Math.max(positiveMax, -negativeMin);
    }
    //最大子数组和
    public static int maxSubArray(int[] nums) {
        int len = nums.length;
        // dp[i] 表示：以 nums[i] 结尾的连续子数组的最大和
        int[] dp = new int[len];
        dp[0] = nums[0];

        for (int i = 1; i < len; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
        }

        // 也可以在上面遍历的同时求出 res 的最大值，这里我们为了语义清晰分开写，大家可以自行选择
        int res  = Arrays.stream(dp).max().getAsInt();
//        int res = dp[0];
//        for (int i = 1; i < len; i++) {
//            res = Math.max(res, dp[i]);
//        }
        return res;
    }
    //优化版
    public static int maxSubArray2(int[] nums) {
        int pre = 0;
        int res = nums[0];
        for (int num : nums) {
            pre = Math.max(pre + num, num);
            res = Math.max(res, pre);
        }
        return res;
    }
    /*
    int maxSubArray(int* nums, int numsSize) {
    // int dp[numsSize];
    // memset(dp, 0, sizeof(dp));
    // dp[0] = nums[0];
    // int max = nums[0];
    // for(int i=1;i<numsSize;i++){
    //     if(dp[i-1]>0){
    //         dp[i] = dp[i-1]+nums[i];
    //     }else{
    //         dp[i] = nums[i];
    //     }
    //     max = fmax(max,dp[i]);
    // }
    int max = nums[0];
    int pre =0;
    for(int i=0;i<numsSize;i++){
        pre = fmax(pre+nums[i],nums[i]);
        max = fmax(max,pre);
    }
    return max;
}
     */
    //分治1.0
    public static int maxSubArray_dc(int[] nums) {
        return maxSubArrayDivide(nums, 0, nums.length - 1);
    }
    private static int maxSubArrayDivide(int[] nums, int left, int right) {
        // 基本情况：当数组只有一个元素时，最大子数组和就是该元素本身
        if (left == right) {
            return nums[left];
        }

        // 找到中点
        int mid = left + (right - left) / 2;

        // 递归计算左半部分的最大子数组和
        int maxLeft = maxSubArrayDivide(nums, left, mid);
        // 递归计算右半部分的最大子数组和
        int maxRight = maxSubArrayDivide(nums, mid + 1, right);

        // 计算跨越中点的最大子数组和
        int maxCrossing = maxCrossingSum(nums, left, mid, right);

        // 返回三个结果中的最大值
        return Math.max(Math.max(maxLeft, maxRight), maxCrossing);
    }

    private static int maxCrossingSum(int[] nums, int left, int mid, int right) {
        // 初始化左半部分和右半部分的最大和
        int maxLeftSum = Integer.MIN_VALUE;
        int maxRightSum = Integer.MIN_VALUE;
        int sum = 0;

        // 计算左半部分的最大和
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            maxLeftSum = Math.max(maxLeftSum, sum);
        }

        // 重置sum用于计算右半部分的最大和
        sum = 0;
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            maxRightSum = Math.max(maxRightSum, sum);
        }

        // 返回跨越中点的最大子数组和
        return maxLeftSum + maxRightSum;
    }
    //分治法  有bug
    public static int maxSubSum(int[] arr, int left, int right) {
        int sum;
        if (left == right) {
            sum = Math.max(arr[left], 0);
        }else{
            int mid = left + (right - left) / 2;
            int leftSum = maxSubSum(arr, left, mid);
            int rightSum = maxSubSum(arr, mid+1, right);
            int leftMax = 0, left_flag = 0;
            for (int i = mid; i >= left; i--) {
                left_flag += arr[i];
                if(left_flag>leftMax){
                    leftMax = left_flag;
                }
            }
            int rightMax=0,right_flag=0;
            for (int i = mid+1; i < right; i++) {
                right_flag+=arr[i];
                if (right_flag > rightMax) {
                    rightMax = right_flag;
                }
            }
            sum = leftMax + rightMax;
            sum = Math.max(Math.max(sum, leftSum), rightSum);
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = {5,4,-1,7,8};
        System.out.println(maxSubArray_dc(nums));
        System.out.println(maxSubArray2(nums));
        System.out.println(maxSubSum(nums, 0, nums.length - 1));
    }
}
